package cn.dapeng.bitmap;

import java.util.HashSet;

/**
 * 位图：极大的节省内存空间
 * <p>
 * <p>
 * max / 64 决定该数字放在数组的哪个位置
 * max % 64 决定放在那个bit位上
 */
public class BitMap {

    private final long[] bits;

    public BitMap(int max) {
        // 相当于 （max + 64） / 64
        bits = new long[(max + Long.SIZE) >> 6];
    }

    /**
     * 添加
     *
     * @param num
     */
    public void add(int num) {
        // bits[num / 64] = bits[num / 64] | (1 << (num % 64))
        /**
         * 注意这个1L 和 1的区别， 一个是64位 一个是32位
         */
        bits[num >> 6] |= (1L << (num & 63));
    }

    /**
     * 删除
     *
     * @param num
     */
    public void delete(int num) {
        // bits[num / 64] = bits[num / 64] & (1 << (num % 64))
        bits[num >> 6] &= ~(1L << (num & 63));
    }

    public boolean contain(int num) {
        return (bits[num >> 6] & (1L << (num & 63))) != 0;
    }

    /**
     * 对数器
     *
     * @param args
     */
    public static void main(String[] args) {
        int max = 10000;
        int testTimes = 10_0000;
        BitMap bitMap = new BitMap(max);
        HashSet<Integer> set = new HashSet<>();
        for (int i = 0; i < testTimes; i++) {
            int num = (int) (Math.random() * max + 1);
            double decide = Math.random();

            if (decide < 0.333) {
                bitMap.add(num);
                set.add(num);
            } else if (decide < 0.666) {
                bitMap.delete(num);
                set.remove(num);
            } else {
                if (bitMap.contain(num) != set.contains(num)) {
                    System.out.println("Oops");
                    break;
                }
            }

        }

        for (int num = 0; num <= max; num++) {
            if (bitMap.contain(num) != set.contains(num)) {
                System.out.println("Oops");
                break;
            }
        }
    }

}
